package com.ljy.algorithm;

import java.util.*;
import java.util.Scanner;

public class DijKstra {
  public static void main(String[] args) {
    MD md = new MD();
    Scanner sc=new Scanner(System.in);    
    System.out.println("几个点？");    
    int m=sc.nextInt();    
    int[][]data=new int[m][m];
/*
例:（10个点）    
1 2 3
2 3 3
3 4 7 
4 10 2 
3 10 5 
2 6 3 
6 10 2 
2 5 2 
5 6 3 
8 6 1
8 10 2
8 9 2
9 10 4
7 8 3
7 9 2
1 7 4
*/
    for(int i=0;i<m;i++){
      for(int j=0;j<m;j++){
        if(j==i)data[i][j]=0;
        data[i][j]=-1;
      }
    }
    System.out.println("输入边的起点、终点、权值,以非正数结束");    
    int count=0,i,j,p;
    while(true){
      System.out.println("第"+(++count)+"条"); 
      i=sc.nextInt()-1;   
      if(i<0){
        break;
      }
      j=sc.nextInt()-1;   
      p=sc.nextInt(); 
      data[i][j]=p;
    }        
    /*int[][]data =
        new int[][] {
          {0, 4, -1, -1, 1, -1, 3, -1},
          {-1, 0, -1, -1, 1, -1, -1, -1},
          {-1, 2, 0, -1, -1, 4, -1, -1},
          {-1, -1, 6, 0, -1, -1, -1, 7},
          {-1, -1, -1, -1, 0, 6, -1, -1},
          {-1, -1, -1, -1, -1, 0, -1, 3},
          {-1, -1, -1, -1, 4, -1, 0, -1},
          {-1, -1, -1, -1, -1, -1, 1, 0}
        };*/
    System.out.println("原始矩阵:");
    for(int[]d:data) {
      System.out.println(Arrays.toString(d).replaceAll("-1","_")); 
    }
    md.main(data);
    //md.visitPl();
  }
}

class MD {
  // 所有下标从0开始
  int[][] data; // 图的二维数据
  Map<Integer, Integer> map = new HashMap(); // 键是v(j)，值是v(j)的上一个v(i)
  Map<Integer, int[]> pl = new HashMap(); // 键是v，值是p， lambda

  public void main(int[][]data) {
    this.data=data;
    // 初始化
    pl.put(0, new int[] {0, 0});
    // 找v0能到达的位置
    List<Integer> end = findEnd(0);
    // 标记p
    setP(0, end);
    // 选最小vi，给标记lambda，记录标记的集合
    List<Integer> min = findMin();
    StringBuilder sb = new StringBuilder();
    for (int i : min) {
      sb.append("v" + (i + 1) + "  ");
    }
    System.out.println("第" + 1 + "次最小值是" + sb.toString());
    setLambda(0, min);
    // 找vi能到达的位置
    // 找最小，标记lambda
    int t = 1;
    while (true) {
      if (t++ >= 20) {
        break;
      }
      for (int i : min) {
        // 找v(i)能到达的位置
        end = findEnd(i);
        // 标记p
        setP(i, end);
      }
      // 选最小vi，给标记lambda，记录标记的集合
      min = findMin();
      if (min.size() == 0) {
        System.out.println("最终结果是:");
        visitPl();
        break;
      }
      visitPl2();
      sb.setLength(0);
      for (int i : min) {
        if(i==data.length-1){
          System.out.println("第"+t+"次已找到最优路径，接下来给尽可能多的点进行P标号");
        }
        sb.append("v" + (i + 1) + "  ");
      }
      System.out.println("第" + t + "次最小值是" + sb.toString());
      for (int i : min) {
        setLambda(map.get(i), i);
      }
    }
  }

  // 用于标记lambda，传入起点和要设置lambda的终点
  void setLambda(int i, List<Integer> end) {
    for (int key : end) {
      int[] aPl = pl.get(key);
      aPl[1] = i; // 表示从v(i)来的
    }
  }
  //单个设置
  void setLambda(int i, int j) {    
    int[] aPl = pl.get(j);
    aPl[1] = i; // 表示从v(i)来的    
  }

  // 返回的是i，表示第v(i)上的数字最小
  List<Integer> findMin() {
    List<Integer> ans = new ArrayList<>();
    int min = -1;
    Set<Integer> set = pl.keySet();
    int[] a;
    // 找到没有标lambda的最小p对应的vj
    for (int j : set) {
      a = pl.get(j);
      // 等于-1表示还没赋值lamda
      if (a[1] == -1) {
        // min还没赋值，给赋初值
        if (min == -1) {
          min = a[0];
          ans.add(j);
        } else {
          // 当前不是最小的，从新找
          if (min > a[0]) {
            min = a[0];
            ans = new ArrayList<>();
            ans.add(j);
          }
          // 加入多个
          else if (min == a[0]) {
            ans.add(j);
          }
        }
      }
    }
    return ans;
  }
  // 标记p(i)
  void setP(int i, List<Integer> end) {
    int pi = pl.get(i)[0]; // 获取到v0到i的距离
    int pj;
    int[] p;
    // 先获取每个终点对应的pl值
    for (int j : end) {
      pj = pi + data[i][j]; // v0到j的距离
      // 没有，那么就直接赋新的p
      if (!pl.containsKey(j)) {
        pl.put(j, new int[] {pj, -1});
        // 增加一对终点-起点的
        map.put(j, i);
      }
      // 有，比较，赋较小的值
      else {
        p = pl.get(j);
        if (p[1] == -1) { // 表示还没赋值lambda,赋值过，不用管
          if (p[0] > pj) {
            p[0] = pj;
            // 改变映射
            map.remove(j);
            map.put(j, i);
          }
        }
      }
    }
  }
  // 找v(i)的终点
  List<Integer> findEnd(int i) {
    List<Integer> ans = new ArrayList<>();
    // 也就是找第i行不为-1的数字
    for (int j = 0; j < data.length; j++) {
      if (data[i][j] != -1 && data[i][j] != 0) {
        ans.add(j);
      }
    }
    return ans;
  }

  void visitPl() {
    Set<Integer> set = pl.keySet();
    System.out.println("v1-->");
    for (int key : set) {
      int[] p = pl.get(key);
      if (p[1] != -1) {
        System.out.println("\tv" + (1 + p[1]) + " --> v" + (1 + key) + "：" + p[0]);
      } else {
        System.out.println("\t未知 --> v" + (1 + key) + "：" + p[0]);
      }
    }
    System.out.println();
  }
  void visitPl2() {
    Set<Integer> set = pl.keySet();    
    for (int key : set) {
      int[] p = pl.get(key);
      if (p[1] != -1) {
        System.out.println("v"+(key+1)+" p：" + p[0]+" λ:"+(1+p[1]));
      } else {
        System.out.println("v"+(key+1)+" p：" + p[0]+" λ:M");
      }
    }
    System.out.println();
  }
}
